Modern search engines typically provide users with sets of search results that are responsive to a received query. The search results often include links to web pages or other resources that the search engine purports to be related to the received query. Typically, the search engine provides the search results in a ranked form, so that the user may focus on the search results that are deemed to be the best search results.
Many methods for ranking search results exist. For example, the rank of a web page may be based on the number of other web pages that link to it. Thus, a web page that has more web pages that link to it will have a higher rank then a web page that has fewer web pages that link to it.
The relationship between web pages in the Internet may be represented by a directed graph. The graph may include nodes that represent web pages and edges that represent links to web pages. The rank of the web pages represented by the nodes of the graph may then be calculated from the graph. Because the number of nodes in these graphs is often large, the graphs are typically not stored in main memory, but are presented as a graph stream. The rank of the nodes in the graph is then computed by making multiple passes over the graph stream. Current techniques for computing the rank of nodes from a graph stream having n nodes may use O(n) memory space and O(M) passes of the graph stream where M is the mixing time of the graph.